Now that we've seen how the visited set is a crucial safeguard against cycles, let's analyze a full implementation of Prim's algorithm. Below is a function that attempts to find the MST for our Shared_Graph.

  • However, this version contains a subtle but critical logic bug. It produces the correct output for this specific graph but is deeply flawed. Your challenge is to identify the conceptual error in the code.
  • Instructions:
    • Trace the execution of the code, either mentally or by running it.
    • Pay close attention to the state of the priority queue (pq) and the visited set at each step.
  • The bug is not a syntax error; it's an inefficiency that violates a core principle of the algorithm and would cause incorrect results on other graphs. What is being added to the priority queue that shouldn't be?
Python Implementation (Buggy Prim's)
1import heapq
2
3# Adjacency list for the Shared_Graph
4shared_graph_adj = {
5    'A': [('B', 4), ('C', 3)],
6    'B': [('A', 4), ('C', 1), ('D', 5)],
7    'C': [('A', 3), ('B', 1), ('D', 2), ('E', 6)],
8    'D': [('B', 5), ('C', 2), ('E', 8), ('F', 7)],
9    'E': [('C', 6), ('D', 8), ('F', 9)],
10    'F': [('D', 7), ('E', 9)],
11}
12
13def prims_buggy(graph, start_node):
14    visited = set()
15    pq = [(0, start_node, None)] # (weight, current_vertex, from_vertex)
16    mst_edges = []
17    total_cost = 0
18
19    while pq and len(visited) < len(graph):
20        weight, u, prev = heapq.heappop(pq)
21
22        if u in visited:
23            continue
24        
25        visited.add(u)
26        if prev is not None:
27            mst_edges.append((prev, u, weight))
28            total_cost += weight
29        
30        # *** HINT: The bug is in this loop ***
31        for v, edge_weight in graph[u]:
32            heapq.heappush(pq, (edge_weight, v, u))
33
34    return mst_edges, total_cost
35
36mst, cost = prims_buggy(shared_graph_adj, 'A')
37print(f"MST Edges: {mst}")
38print(f"Total Cost: {cost}")